package puzzle.projecteuler.p100;


public class Problem100 {

	/**
	 * 
	 * 本问题可以转化为求b(b-1) = x(x-1)/2的最小满足x>10^12的解
	 * <=> X^2 - 2*B^2 = -1, X=2x-1, B=2b-1
	 * 
	 * 参考Problem066，关于Pell方程的解法
	 * 
	 * X + B*sqrt(2) = [1+1*sqrt(2)]^(2n+1)
	 * => X(n) = 3*X(n-1) + 4*B(n-1)
	 *    B(n) = 3*B(n-1) + 2*X(n-1)
	 * @param args
	 */
	public static void main(String[] args) {
			
		long X = 1;
		long B = 1;
		while (true) {
			long t = X;
			X = 3*X + 4*B;
			B = 3*B + 2*t;
			System.out.println((X+1)/2 + "," + (B+1)/2);
			if ((X+1)/2 > 1000000000000L) {
				break;
			}
		}
		System.out.println((B+1)/2);
	}
}
